from collections import OrderedDict


class LRUCache:
    def __init__(self, capacity: int):
        self.cache = OrderedDict()
        self.capacity = capacity

    def get(self, key: int) -> int:
        if key not in self.cache:
            return -1
        # 将访问的键移到字典末尾（表示最近使用）
        self.cache.move_to_end(key)
        return self.cache[key]

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            # 如果键已存在，先移到末尾再更新值
            self.cache.move_to_end(key)
        self.cache[key] = value
        # 如果超出容量，弹出最久未使用的键（字典开头）
        if len(self.cache) > self.capacity:
            self.cache.popitem(last=False)


if __name__ == '__main__':
    # 测试用例
    cache = LRUCache(2)
    cache.put(1, 1)
    cache.put(2, 2)
    print(cache.get(1))  # 输出: 1
    cache.put(3, 3)  # 容量已满，键2被淘汰
    print(cache.get(2))  # 输出: -1 (未找到)
